Field of the Invention
The invention relates to a scheduler for a memory system, which signals to a data processing unit that data to be stored in the memory system is stored for a time period that is defined by the user.
FIG. 1 shows the fundamental configuration for data processing. Data is emitted in parallel or serial form from a data source to a data processing unit, which processes the data in accordance with a calculation rule, and emits the processed data to a downstream data sink.
The data stream arrives in accordance with a data arrival curve at the data input of the data processing unit. FIG. 2 shows a linear or ideal data arrival curve. In the case of actual data transmission, the data arrival curve is not linear, but has different gradients and discontinuities that, for example, originate from data bursts.
The data processing unit processes the data in accordance with a data-operating curve, which is illustrated in FIG. 2. If, as in the case of the example illustrated in FIG. 2, more data arrives at the input E of the data processing unit than can be processed by the data processing unit, a buffer store must be provided at the input E of the data processing unit to buffer-store the excess data. The minimum memory size of the buffer store corresponds to the maximum difference between the arrival curve and the operating curve. The data that is processed in the data processing unit must be made available to the downstream data sink within a predetermined delay time ΔT. The data stream that arrives in the data processing unit must be signaled, after a predetermined delay time ΔT, to the downstream data sink as data to be retrieved. The data remains available in the time period between the arrival time of the data and the emission time, when the time delay reaches the desired time delay value ΔT. Once this time interval or time period has elapsed, the data that has not been passed on to the data sink and/or processed is either sent immediately with priority, is moved to a different storage location, or is deleted. The data source produces the data stream (traffic) with an arrival curve, which is virtually linear in places, at the output of the data source. The data stream is modified by the data transmission channel. The data processing unit emits the received data after the predetermined time delay “ΔT”. In such a case, it is desirable for the linear arrival curve of the data source to be reconstructed with a predetermined time delay at the output A of the data processing unit. The data stream data that is emitted from the data processing unit may be routed to different data sinks. In a practical application, it is necessary to implement a time out for the arriving data within a memory administration system to avoid jamming or deadlock situations. Once the time out “ΔT” has elapsed, the buffer-stored data must either be deleted or moved to another memory to release the memory space in the buffer store. To comply with quality of service requirements, it is, in such a case, important to maintain a deterministic, predetermined, accurate time delay “ΔT”.
In the case of a so-called time stamping according to the prior art, each arriving data packet DP in the data stream that arrives at the input E of the data processing unit is provided with a time stamp, which indicates the arrival time at the input E. The arriving data packet DP is read, and the time of arrival of the data packet is measured. The measured data arrival time is stored as a time stamp in a table. A periodic check is, then, carried out to determine whether or not the received data packet has already been in the data processing unit for longer than the predetermined delay time AT. Those data packets whose time out has been reached are, then, deleted or stored elsewhere.
One serious disadvantage in the case of time stamping is that a data stream that includes a large number of data packets must be administered by the data processing unit with a corresponding number of time stamps. On one hand, an associated memory space must be provided for each time stamp and, furthermore, a very large number of time comparison processes are required. Thus, the circuitry complexity within the data processing unit increases considerably if the comparisons of the various time stamps are intended to be carried out at the same time. If the time comparisons are carried out sequentially due to the large number of time stamps, the inaccuracy with respect to the delay time ΔT increases.
A so-called time wheel memory administration method has, therefore, been proposed according to the prior art. FIG. 3 shows a configuration to explain the time wheel method. A data processing unit receives from a scheduler the information to retrieve the data to be processed from the memory system. The scheduler is connected to two data sources A, B through a network. In the example illustrated in FIG. 3, each data source sequentially emits five data packets to the network. The data packets or data cells are, for example, ATM data cells with a predetermined data size of 53 bytes. The five ATM data cells are fragmented in order to fragment a relatively large data packet. In such a case, the large data packet is received and is fragmented into smaller cells, and the fragmented cells are, then, transmitted through the network to a data processing unit. The data processing unit joins the received data cells together to recreate the original data packet.
The ATM cells that are transmitted through the network arrive in an undefined sequence at the scheduler, which writes them to the memory system. If the memory system has a relatively large size SP0, the data cells A to E from the first data source A and the data cells α to ε from the second data source B are, by way of example and as illustrated in FIG. 3, written to the memory system using a FIFO method.
A problem occurs if the memory size of the memory system is relatively small, for example, SP1. In such a case, it is impossible to write a complete string (for example, including five ATM cells) to the memory system. Once the ATM cell 6 from the second data source B has been written to it, the memory system is full, and the scheduler has to decide, when the next ATM cells ε, D, E arrive, that already stored ATM cells must be deleted within the memory system to allow a complete ATM cell string (which can subsequently be processed appropriately through the data processing unit) to be buffer-stored in the memory system. The scheduler can, thus, delete or change the memory locations of data packets in accordance with a strategy or a policy or if the memory system is full and further data packets arrive. For example, the scheduler could delete the first data packet A that arrived to create memory space for the next arriving data packet ε. In such a case, the complete string of ATM cells from the data source B would be buffer-stored in the memory system, and would be available for data processing by the data processing unit. An alternative strategy is the complete deletion of all received data cells from a data source, for example, the data cells α, β, γ, δ from the data source B, to create memory space for the two arriving data cells D, E so that the data processing unit can process the data in the data source A, that is to say, the ATM cells A to E.
In the case of the time wheel method, which is illustrated in FIG. 3, the arriving ATM cells are stored in the sequence in which they arrive. The memory system is a FIFO memory. In the case of the time wheel method, the memory occupancy of the memory system is used as a measure of the time. For such a purpose, the data is stored in a conventional manner in a circular FIFO data buffer. If an arriving data cell is buffer-stored at a location X, the next data or data packets is or are stored at memory locations that follow the memory location X. As such, the FIFO memory is filled successively until the filed memory space reaches a specific level, or the memory is completely filled with data. If the amount of arriving data is recorded and the data arrives at a predetermined data rate R, it is possible to calculate the time that has passed since the data packet DP at the position X is buffer-stored. Because the memory full level corresponds to the time out of the buffer-stored data cell, or of the buffer-stored data packet, the scheduler can signal to the data processing unit that the previously stored data packet has timed out, as soon as the memory full level is reached.
One disadvantage of the time wheel method is that the arriving data stream is only rarely at a constant, uniform data rate R. In many applications, there are time gaps between the arrival of the various data cells or data packets. Because the data rate is assumed to be constant for calculation purposes, due to the fact that data transmission rates fluctuate widely in some cases, this results in the calculation of the time out being very inaccurate.
An improved time wheel method (enhanced time wheel) has, thus, been proposed, in which time gaps between the arrival of data packets are bridged by so-called dummy cells or filling data cells. If no data packet or no data cell arrives at the scheduler within a variable waiting time, the scheduler writes a filling data cell to the FIFO memory in the memory system.
FIG. 4 shows, schematically, a FIFO memory in which a sequence of ATM cells Z1, Z2, Z3, Z4 have been written in accordance with the sequence of their arrival. The ATM cells are linked to one another by pointers and have a fixed data size of 53 bytes. The data processing unit uses the linking process to identify that the ATM cells have originated from the same data source. If the time difference between the arrival of an ATM cell Z1 and a second ATM cell Zi+1 exceeds a specific waiting time, the scheduler writes a filling cell to the FIFO memory. As soon as the FIFO memory is full, those ATM cells that arrived first and, thus, represent the oldest ATM cells are deleted or are written to another memory. The provision of dummy or filling cells increases the accuracy in the calculation of the time out because the filling cells reflect the time during that no ATM data cells were received by the scheduler.
One disadvantage of the procedure illustrated in FIG. 4 is the so-called internal fragmentation. The data cells have a fixed data size. If, by way of example, the data cells are ATM data packets or ATM data cells, the data cells include 53 bytes. The filling data cells are of the same size as the data cells, that is to say, the filling data cells, likewise, include 53 bytes. In the case of the enhanced time wheel method, as is illustrated in FIG. 4, if, for example, an IP data packet with a size of 54 bytes is received and this is converted in a protocol conversion process to a sequence of ATM data cells, this results in a first data cell with 53 bytes and a second ATM data cell that contains only 1 byte of payload data. The other 52 bytes from the second ATM data source, which do not contain any payload data, likewise, lead to occupancy of memory space within the FIFO memory and, thus, to memory wastage.
The smaller the size of the data cells or data fragments is chosen to be, the greater is the proportion of the overhead or header data in the cells in comparison to the stored payload data. Furthermore, there is an increase in the data length of the pointers that are contained in the data cells and ensure that the cells are linked to one another. The larger the memory cells that are used, the more memory space is wasted, however, due to the fragmentation process and the greater is the inaccuracy of the calculated time out. If the cell size is reduced, much less memory space is wasted for the fragmented payload data, but more memory space is wasted for the overhead or header data in the data cells.